package baseclass.d_list;


import utils.DoubleNode;
import utils.ListNode;
import utils.ListUtil;

/**
 * @date 2020/2/27 23:39
 */
public class Code02_ReverseList {
    /**
     * 题目1：翻转单向链表
     */
    public static ListNode reverseList(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode pre = null;
        while (head != null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    //方式2：使用容器保存顺序节点，然后反关联，空间O(n)

    /**
     * 题目2：翻转双向链表
     */
    public static DoubleNode reverseList(DoubleNode head){
        if(head == null || head.next == null) return head;
        DoubleNode pre = null;
        while (head != null){
           DoubleNode next = head.next;
           //改变当前节点的前驱和后继
            head.next = pre;
            head.pre = next;
            //记录当前节点为下一次的上个节点
            pre = head;
            head = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        ListUtil.printLinkedList(head1);
        head1 = reverseList(head1);
        ListUtil.printLinkedList(head1);

        DoubleNode head2 = new DoubleNode(1);
        head2.next = new DoubleNode(2);
        head2.next.pre = head2;
        head2.next.next = new DoubleNode(3);
        head2.next.next.pre = head2.next;
        head2.next.next.next = new DoubleNode(4);
        head2.next.next.next.pre = head2.next.next;
        ListUtil.printDoubleLinkedList(head2);
        ListUtil.printDoubleLinkedList(reverseList(head2));

    }

}
